1. Technical Field
The present disclosure pertains to the field of memory management and in particular, to systems and methods for managing data in complex memory containers.
2. Description of Related Art
Document processing software, database management systems, computer graphics, document printing, and other software applications often use complex memory containers to hold data for processing. These complex containers, which can include code and data, permit representation of multiple relationships between various objects (or portions of these objects) that are held in the containers.
For example, during document processing Page Description Language (“PDL”) descriptions, which provide a high-level portrayal of each page in a document, may be parsed and converted to an intermediate form—termed a display list—prior to rasterization. The display list (“DL”), which can hold objects, including commands called display list primitives, is a type of complex container with an elaborate data structure. In some instances, the DL may be comprised of a linked list of linked lists, with the nodes of the latter referencing memory blocks, which, in turn, may contain data from multiple graphical objects. Partly on account of this complexity, the internal structure of complex containers (such as the display list) is typically hidden from its clients and the complex container (hereinafter “container”) may provide an external functional interface to clients to add entire objects, or object data to the container. The functional interface often specifies that the object or object portions to be added to the container be placed in a contiguous memory block prior to invocation of the functional interface.
In some instances, however, such as during print data processing, specific portions of graphical objects, which are not contiguous in memory, may be selected for addition to the display list. In other words, each portion of the graphical object selected for addition to the DL may reside in a memory location that is not contiguous with any other selected portion of the same graphical object i.e. the object portions are mutually discontiguous.
In traditional schemes, when non-contiguous portions of graphical objects are selected for addition to a DL, the DL functional interface may be called multiple times to add each distinct portion. In such situations, it becomes difficult for the program code associated with the DL functional interface to guarantee the atomicity of the transaction as a whole. For example, memory may be unavailable after one portion of the graphical object has been written to the DL.
Another approach calls the functional interface associated with the DL to add the entire graphical object to the DL. However, adding the entire graphical object to the DL can be an extremely inefficient use of memory resources because the portions of the graphical object selected for addition to the DL may be small in size relative to the size of the entire object. A third approach copies the selected portions of the graphical object in sequence into a contiguous memory block and prior to invoking the functional interface to add the memory block to the DL. The additional copy step contributes to processing delays.
In general, conventional schemes for the addition of mutually discontiguous data items to complex containers in a given order use memory inefficiently, may be slow, and/or incapable of guaranteeing the atomicity of the entire transaction. Thus, there is a need for systems and methods to efficiently allow the addition of non-contiguous data items to containers while guaranteeing the atomicity of the entire transaction.